/**
 * Copyright 2011 Joe Choi, All rights reserved.
 */
package tao.data.structure.tree;

import static tec.data.structure.DataStructure.stack;

import java.util.ArrayList;
import java.util.List;

import tao.data.structure.Stack;
import tao.data.structure.tree.ConcreteBuilder.AbstractHandler;
import tao.data.structure.tree.Traversal.Event;

/**
 * To build a tree by refers the content and structure of a given tree in PostOrder
 * 
 * @author Joe Choi
 */
public class PostOrderBuildHandler<S, V, T extends Tree<V>> extends AbstractHandler<S, V, T> {
	public PostOrderBuildHandler(Tree<S> source, Creation<S, V, T> creation) {
		setSource(source);
		this.creation = creation;
		subtreeList = stack();
	}

	@Override
	public final Traversal<S> getTraversal() {
		return(new PostOrderTraversal<S>(source));
	}

	@Override
	public void beforeTraverseSubtree(Event<S> event) {
		subtreeList.push(new ArrayList<T>());			
	}
	
	@Override
	public void traversedTree(Event<S> event) {
		Tree<S> node = event.getTree();
		List<T> subtree = subtreeList.pop();
		T newNode = creation.create(node, subtree);
		
		if(subtreeList.top() != null) {
			subtreeList.top().add(newNode);
		} else {
			root = newNode;			
		}
	}

	private Stack<List<T>> subtreeList;
	private Creation<S, V, T> creation;

	/**
	 * Create a specific type tree
	 */
	public interface Creation<S, V, T extends Tree<V>> {
		public T create(Tree<S> node, List<T> subtree);
	}	
}